// OpentTxl-C Version 11 parse tree representation
// Copyright 2023, James R. Cordy and others

#ifdef TXLMAIN
// Initialization
extern void tree (void);
#endif

// Tree nodes and kids are represented by their integer indices in the trees(void) and kids() arrays respectively
// typedef int treePT;  % defined in tokens.i   
typedef int kidPT;

// Null tree and kid indices
#define nilTree 0
#define nilKid  0

// Tree availability flag for use in garbage collection - any positive number not in the legal range
#define AVAILABLE 999999999
#define NILMARK   -AVAILABLE

typedef unsigned short countT;

// Used in grammar analysis
enum derivesT {
    derivesT_yes, derivesT_no, derivesT_dontknow
};

// Tree node type
struct  parseTreeT {
    // order of these fields matters, to minimize node size
    enum treeKindT  kind;
    enum derivesT   derivesEmpty;   // used only in grammar analysis
    countT          count;          // how many children, or number of choice alternative
    tokenT          name;           // normalized name or literal value
    tokenT          rawname;        // original name or literal value
    kidPT           kidsKP;         // list of children, or 'each' indicator
};

// Tree and kids arrays, allocated dynamically
// We assume that trees and kids are initialized to 0 when allocated
extern array (treePT, tree_kids);
extern array (struct parseTreeT, tree_trees);

// Numbers of trees and kids currently in use
extern int tree_treeCount;
extern int tree_kidCount;
extern void tree_setTreeCount (const int count);
extern void tree_setKidCount (const int count);
extern int tree_maxTreeCount;

// Current allocation strategy
// two are implemented - 
//      simple = haven't run out yet, so linearly use unused cells
//      scavenge = have done a garbage collection, so search for first fit
extern int tree_allocationStrategy;
#define simple          0
#define scavenge        1
extern void tree_setAllocationStrategy (const int strategy);

// next free tree/kid search starting point (when scavenging)
// extern int tree_lookTree;
// extern int tree_lookKid;

// Error message construction outside of procedures, to avoid using stack space
extern string outOfTreesMessage;
extern string outOfKidsMessage;

extern treePT tree_newTree (void);
extern treePT tree_newTreeInit (const enum treeKindT kind, const tokenT name, const tokenT rawname, const countT count, const kidPT kidsKP);
extern treePT tree_newTreeClone (const treePT ot);
extern void tree_cloneTree (const treePT nt, const treePT ot);

extern void tree_setKind (const treePT t, const enum treeKindT kind);
extern void tree_setName (const treePT t, const tokenT name);
extern void tree_setRawName (const treePT t, const tokenT rawname);
extern void tree_setKids (const treePT t, const kidPT kidsKP);
extern void tree_setCount (const treePT t, const countT count);
extern void tree_setDerivesEmpty (const treePT t, const enum derivesT setting);

extern kidPT tree_newKid (void);
extern kidPT tree_newKids (const countT count);

extern void tree_setKidTree (const kidPT k, const treePT t);

extern treePT tree_firstUserTree;
extern kidPT  tree_firstUserKid;
extern void tree_beginUserTreeSpace (void);

// General tree operations

// Fast whole tree operations - used in transformer and predefineds   
extern bool tree_sameTrees (const treePT tree1TP, const treePT tree2TP);
extern void tree_copyTree (const treePT originalTP, treePT *copyTP);

// General tree operations - used everywhere
extern treePT tree_kidTP (const int which, const treePT parentTP);
extern treePT tree_kid1TP (const treePT treeP);
extern treePT tree_kid2TP (const treePT treeP);
extern treePT tree_kid3TP (const treePT treeP);
extern treePT tree_kid4TP (const treePT treeP);
extern treePT tree_kid5TP (const treePT treeP);
extern treePT tree_kid6TP (const treePT treeP);
extern treePT tree_kid7TP (const treePT treeP);

extern void tree_makeOneKid (const treePT parentTP, const treePT babyTP);
extern void tree_makeTwoKids (const treePT parentTP, const treePT buddyTP, const treePT sisTP);
extern void tree_makeThreeKids (const treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP);
extern void tree_makeFourKids (const treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP, const treePT kid4TP);
extern void tree_makeFiveKids (const treePT parentTP, const treePT kid1TP, const treePT kid2TP, const treePT kid3TP, const treePT kid4TP, const treePT kid5TP);

extern bool tree_plural_emptyP (const treePT pluralTP);
extern treePT tree_plural_firstTP (const treePT pluralTP);
extern treePT tree_plural_restTP (const treePT pluralTP);

// Extract a subtree
extern void tree_extract (const tokenT XT, const tokenT repeatXT, const treePT scopeTP, const bool mustCopy, const bool recursive, treePT *resultRepeatTP);

// Fast deep substitute
extern void tree_substitute (const treePT oldTP, const treePT newTP, treePT *scopeTP);
extern void tree_substituteLiteral (const treePT oldTP, const treePT newTP, treePT *scopeTP);

// Tree operations used everywhere
extern bool tree_isListOrRepeat (const treePT listOrRepeatTP);
extern int tree_lengthListOrRepeat (const treePT listOrRepeatTP);
extern bool tree_isEmptyListOrRepeat (const treePT listOrRepeatTP);
extern treePT tree_listOrRepeatFirstTP (const treePT listOrRepeatTP);
extern treePT tree_listOrRepeatRestTP (const treePT listOrRepeatTP);
extern bool tree_isListOrRepeatType (const tokenT listOrRepeatType);
extern tokenT tree_listOrRepeatBaseType (const tokenT listOrRepeatType);
extern bool tree_treeIsTypeP (const treePT treeP, const tokenT typeT);
extern tokenT tree_literalTypeName (const enum treeKindT kind);
